package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * https://leetcode.com/problems/combination-sum/
 * <p>
 * 候选集不重复
 * 候选集中每个元素可以用任意次
 *
 * <p>
 * 这个回溯写的太不正经了
 *
 * @author tzp
 * @since 2020/10/16
 */
public class LC39 implements Backtracking {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return Collections.emptyList();
        backtrackting(candidates, 0, target, new ArrayList<>());
        return result;
    }

    public void backtrackting(int[] candidates, int candidateIndex, int remainTarget, List<Integer> path) {
        int i = 0;
        for (; i * candidates[candidateIndex] <= remainTarget; i++) {
            int newTarget = remainTarget - i * candidates[candidateIndex];
            if (newTarget == 0) {
                result.add(new ArrayList<>(path));
            } else {
                if (candidateIndex + 1 < candidates.length) {
                    backtrackting(candidates, candidateIndex + 1, newTarget, path);
                }
            }
            path.add(candidates[candidateIndex]);
        }
        for (int j = 0; j < i; j++) {
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(new LC39().combinationSum(new int[]{2, 3, 5}, 8));
        System.out.println(new LC39().combinationSum(new int[]{2, 3, 5}, 9));
    }

}
